import java.util.*;

public class Solution {
    public int evalRPN(String[] tokens) {    //逆波兰表达式
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if (isNumber(tokens[i])) {
                stack.push(Integer.parseInt(tokens[i]));
            }else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (tokens[i]) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                        break;
                }
            }
        }
        return stack.pop();
    }
    public boolean isNumber(String token) {
        return !(token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/"));
    }
    public boolean IsPopOrder (int[] pushV, int[] popV) {   //判断栈是否可以以另一个序列出栈
        Deque<Integer> stack = new LinkedList<>();
        int j = 0;
        for (int i = 0; i < pushV.length; i++) {
            while (j < pushV.length && stack.isEmpty() || stack.peek() != popV[i]) {
                stack.push(pushV[j]);
                j++;
            }
            if (stack.peek() == popV[i]) {
                stack.pop();
            }else {
                return false;
            }
        }
        return true;
    }

    public int calPoints(String[] operations) {       //棒球问题
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < operations.length; i++) {
            if (isNumber2(operations[i])) {
                stack.push(Integer.parseInt(operations[i]));
            }else {
                switch (operations[i]) {
                    case "+":
                        int num = stack.pop();
                        int top = stack.peek();
                        stack.push(num);
                        stack.push(num + top);
                        break;
                    case "C":
                        stack.pop();
                        break;
                    case "D":
                        int a = stack.peek();
                        stack.push(2 * a);
                    default:
                        break;
                }
            }
        }
        int count = 0;
        while (!stack.isEmpty()) {
            count += stack.pop();
        }
        return count;
    }
    public boolean isNumber2(String operation) {
        return !(operation.equals("+") ||operation.equals("D") ||operation.equals("C"));
    }

    public boolean backspaceCompare(String s, String t) { //比较含退格的字符串
        return deleteChar(s).equals(deleteChar(t));
    }

    public String deleteChar(String s) {
        StringBuffer ret = new StringBuffer();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (ch != '#') {
                ret.append(ch);
            }else {
                if (ret.length() > 0) {
                    ret.deleteCharAt(ret.length()-1);
                }
            }
        }
        return ret.toString();
    }
}
